Physicians routinely utilize three-dimensional (3D) medical imaging methods to assess hollow, branching organs in patients. Examples of such organs include the liver vasculature, heart vasculature, and the airways of the chest.1-3 Examples of 3D medical imaging modalities used to examine these organs are multidetector computed tomography (MDCT) and magnetic resonance imaging (MRI).4 Often, the physician must find a way to navigate through the organ to reach a target diagnostic region of interest (ROI). The navigation through the organ may be virtual—solely within data derived from the 3D image, or it may be by a device, such as an endoscope, moving through the organ in a follow-on live procedure.1,3,5-7 In each circumstance, an appropriate route through the organ to the target location is often difficult to determine.
Lung cancer is the deadliest form of cancer in the United States, accounting for nearly 30% of all cancer deaths and having a five year survival rate of under 15 percent.8 The current state-of-the-art workflow used to assess lung cancer consists of two phases: (1) acquisition and analysis of 3D volumetric medical images in the form of MDCT scans and (2) bronchoscopy.5,9-11 
During phase 1, the physician manually scrolls through a series of two-dimensional (2D) axial-plane slices of the 3D MDCT image to identify suspect nodules and other abnormalities. Upon determining the 3D location and shape of a specific diagnostic region of interest (ROI), the physician determines an appropriate route through the airway tree—a complex branching structure—to reach the ROI. Defining such a route to suspect peripheral nodules in the chest can be especially challenging because: (1) several airway generations from the trachea need to be traversed, (2) the airway cross-sections are obliquely oriented relative to the given axial-plane data, and (3) the airway tree continually bifurcates as a route is traversed.12-13 
During bronchoscopy, the physician must translate the mentally defined route in the static MDCT data to the dynamic video captured by the endoscope and navigate through the airway tree. Even in the best circumstances, mentally defining the 3D relationships between the endoscope, airways, and target ROI as depicted in the MDCT data and the video feed is difficult. Respiratory motion, coughing, and the inability to view ROIs situated beyond the airway walls make the task even more challenging. Previous research has shown a high degree of variability in bronchoscopy performance between physicians, confirming these difficulties.14 
Computer-based image-analysis techniques can help ease the route-planning task. Image segmentation methods identify image voxels that belong to the airway tree.15-18 Centerline-analysis methods determine the axial structure of the airway tree.19-24 Together, the airway-tree segmentation and centerline-analysis computations provide inputs to 3D visualizations of the airway tree and ROIs. By interacting with different visualization techniques, a route to an ROI can be manually defined. However, even with the additional information provided by the centerline-analysis and segmentation computations, manual route definition is still a challenging task.
The difficulty of manually selecting an appropriate route is illustrated in FIG. 1, wherein route selection is based on the use of an integrated 3D medical image visualization system. The Figure shows two weighted-sum projections of the chest, with the left projection computed in the coronal plane and the right projection computed in the sagittal plane.10 The medial axes of the airway tree, derived from an automated centerline-analysis method of Kiraly et al.,20 and a peripheral ROI are overlaid on the projections. The 3D MDCT image size is 512×512×706 with Δx=Δy=0.67 mm, Δz=0.50 mm (case 21405.3a). A route to the ROI is manually defined by selecting one of the axial paths from the trachea to a peripheral location on the coronal projection. The route is chosen because it appears to approach the ROI in this view. However, it is seen in the sagittal view that this route is inappropriate. The airway terminates in the anterior of the chest, while the ROI is located in the posterior.
The previous example is indicative of the route-planning problem. Even with the assistance of 2D, 3D, and quantitative visualization techniques such as thin-slab visualizations, 3D airway, surface, and ROI renderings, and quantitative plots of airway measurements, manual route planning is difficult.25-28 Centerline-analysis techniques may produce over 200 distinct paths through the major airways. As a result, choosing the best airway path is a daunting task. Furthermore, airway-tree segmentation methods sometimes miss smaller airways, which often could be the ones leading to an ROI. Thus, the extracted paths through the airways can be insufficiently defined to reach a particular ROI.
There has been a great deal of research in extracting centerlines of branching anatomical structures from 3D medical images.19-24 The centerlines provide the physician with information that would otherwise need to be mentally extracted from the volumetric image. They define the topology of the organ and provide a set of potential routes through it. However, the complex branching organs of interest contain many unique paths. Thus, manually searching through a large number of paths to find an acceptable route to an ROI is tedious. Our methods quickly perform this search, determining those paths that provide the most promising routes to the ROI. In cases where no appropriate route exists within the paths as determined by existing centerline-analysis methods, the methods analyze the 3D medical image, augmenting the paths with the locations of previously undetected parts of the branching organ.
The most extensive research previously performed in bronchoscopic-device path planning is by Kukuk, with the goal of defining a set of parameters such as insertion depth, rotation angle, amount of tip deflection, and length of needle insertion to perform a bronchoscopic procedure.29-31 To determine these parameters, the method precisely models the bronchoscope's configuration within the airway tree as it moves toward a pre-determined target position. The method utilizes surfaces derived from an airway-tree segmentation to determine the airway's geometric boundaries. Because the method does not utilize the 3D medical image and instead relies on the surfaces to represent the airway tree, sections of the organ may not be accurately modeled due to imperfections in segmentation techniques. Other inputs include the approximate terminal location of the endoscope within the airway tree (the route destination) and physical endoscope parameters, such as the endoscope diameter, bending radius, and length of the rigid endoscope tip. Using these inputs, the method provides the parameters required to navigate to a particular location. However, the target location is limited to be within the original airway-tree segmentation and is required to be known a priori.
A centerline determination method proposed by Austin included in its calculations the importance of approaching a target ROI “head-on.”32 The method determines paths through sparsely defined centerlines. It is able to determine the location on a discrete path that is nearest an arbitrary location along the path. The nearest discrete path location is chosen so that the path does not overshoot the target location. Our proposed methods build on this idea, determining routes to complex, multiple-voxel ROIs that may extend beyond the original centerline locations.
Similar to the method proposed by Austin, Mori et al. describe a route along an organ's medial axes to a destination that is nearest an arbitrary location in space.33 In this method, the route is augmented with anatomical labels describing the organ segments through which it passes.
Heng et al. proposed an interactive path-generation method that requires user inputs for both the start and end points of a route. By utilizing dynamic programming, this method is able to traverse poor-quality regions in the image when determining paths. However, in regions of poor image quality or weakly defined airways, the user may be required to provide multiple “seed points” to achieve acceptable results. This method, while defining paths robustly, does not fully achieve automated route-planning.
Another method to determine bronchoscopic routes has been proposed by Geiger et al.13 This method seeks to use the pulmonary blood vessels, which they claim are easier to detect in 3D medical images than the airways themselves, as surrogate pathways to ROI locations. The method assumes a close correlation between airway locations and vessel locations. However, the existence or accuracy of this correlation is not guaranteed.
Geiger et. al. have also proposed a visualization method that allows a physician to view the ROI projected onto the airway walls when viewed from an endoluminal location.35 This study forgoes automated route planning, requiring the physician to know the approximate route (bronchoscope) destination, but aids in needle placement. We have used similar techniques in the past, and visualization tools presenting comparable information are incorporated into the route validation phase of our method.10 
Approaches for virtual angiography such as the one proposed by Haigron et al. require little image preprocessing.36 The navigation and route planning is controlled by “active vision,” wherein the appearance of the scene at a particular location drives the navigation decisions of the method. In this approach, segmentation and centerline analysis are essentially done “on the fly,” with the method building up the topology of the branching structure as it progresses toward a pre-defined terminal point. This method may not be able to determine adequate routes if the organ is difficult to segment, as is often the case in airway trees.
Virtual navigation and visualization of the anatomy as depicted in volumetric medical images is the topic of much research.37-40 Often, unlike in the case of bronchoscopy where ROIs must be biopsied to determine their cellular make-up, virtual endoscopy itself is the end goal. This is especially the case in virtual colonoscopy, where the goal is to eliminate the follow-on procedure. The work of Kang et al, seeks to define a path (3D locations and viewing directions) through the colon that is not necessarily an organ centerline. Instead, the path is directed toward polyp detection.42 The method defines paths that are optimized for the virtual fly-through of the colon. The goal is to show each section of the colon wall continuously for as long a period a time as possible so that the physician has an opportunity to detect polyps. In virtual colonoscopy and similar virtual procedures, the methods seek to best define the route to expose ROIs rather than find the best route to navigate to a specific ROI.
The work of Fujii et al. seeks to find appropriate routes for minimally invasive neurosurgery. In this method, voxels within a model brain volume are assigned local costs. These costs correspond to the detrimental effects of different surgical events, such as incisions and contact. The voxel costs are assigned according to the cumulative knowledge of neurological experts.
In summary, there has been a great deal of research that seeks to define “paths” or “routes” through various organs. These paths/routes may exist solely for virtual interrogation of the image or may be defined in a manner that is conducive for follow-on endoscopic procedures. However, there seems to be no method that finds viable paths to precisely-defined ROIs in volumetric images while taking into account the physical properties of the endoscopic device, anatomical constraints, and procedure-specific constraints, and that also allows for the extension of routes beyond the segmentation, if required.